package com.wc.算法基础课.D第四讲数学知识.欧拉函数.最大公约数;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

/**
 * @Author congge
 * @Date 2024/4/11 8:43
 * @description https://www.acwing.com/problem/content/4002/
 */
public class Main {
    static FastReader sc = new FastReader();
    static PrintWriter out = new PrintWriter(System.out);
    static int t;
    static long a, m;

    // 思路：d = gcd(a, m) = gcd(a + x, m)
    //      => a % d = m % d = (a + x) % d = x % d == 0
    //      => 设 a' = a / d, m' = m / d, x' = x / d
    //      => 说明 a' 与 m’ 互质, a' + x' 与 m' 互质
    //      => 相当于求  a' + x' < m' 的互质数的x'的数量
    //      gcd(a' + x', m') == gcd((a' + x') % m' , m')
    //      x' < m' => a' + x' <= a' + m' - 1=> 0 <= (a' + x') % m' <= m' - 1
    //      => 求phi(m') 欧拉函数
    public static void main(String[] args) {
        t = sc.nextInt();
        while (t-- > 0) {
            a = sc.nextLong();
            m = sc.nextLong();
            long d = gcd(a, m);
            out.println(phi(m / d));
        }
        out.flush();
    }

    static long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    static long phi(long n) {
        long res = n;
        for (long i = 2; i <= n / i; i++) {
            if (n % i == 0) {
                while (n % i == 0) n /= i;
                res = res / i * (i - 1);
            }
        }
        if (n > 1) res = res / n * (n - 1);
        return res;
    }
}

class FastReader {
    StringTokenizer st;
    BufferedReader br;

    FastReader() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    String nextLine() {
        String s = "";
        try {
            s = br.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return s;
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }

    // 是否由下一个
    boolean hasNext() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                String line = br.readLine();
                if (line == null)
                    return false;
                st = new StringTokenizer(line);
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return true;
    }
}
